"""
给定数组A和一个正整数X
数组的累乘积末尾0的数量大于等于X视为合法
问A中有多少个连续子段合法
首先将数组元素表示为二元组<2的数量, 5的数量>
然后双指针, 维护left和right
"""
class Solution:
    def getSubarrayNum(self , a , x ):
        n = len(a)
        b = [[0, 0] for i in range(n)]
        for ai, bi in zip(a, b):
            c = 0
            while ai % 2 == 0:
                ai //= 2
                c += 1
            bi[0] = c
            c = 0
            while ai % 5 == 0:
                ai //= 5
                c += 1
            bi[1] = c
        
        ans = 0
        MOD = 1000000000 + 7
        c2 = 0
        c5 = 0
        left, right = 0, 0
        while True:
            while right < n and (c2 < x or c5 < x):
                c2 += b[right][0]
                c5 += b[right][1]
                right += 1
            if c2 < x or c5 < x: break
            ans = (ans + n - right + 1) % MOD

            while left < right:
                c2 -= b[left][0]
                c5 -= b[left][1]
                left += 1
                if c2 >= x and c5 >= x: ans = (ans + n - right + 1) % MOD
                else: break
            
            if n == right: break
       
        ans = ans % MOD
        if ans < 0: ans += MOD
        return ans